Description

$\rm Link$

Solution

一个题目 $\sout{114514}$ 个 $\sout{\text{trick}}$ 你值得拥有

Description

给定一张 $n$ 个点 $m$ 条边的无向图。当你在点 $u$ 时，你可以花费 $1$ 的费用向系统询问当前可以去哪个点，系统会从点 $u$ 的所有出边中随机选择一条告诉你。你可以选择去，或者重新花费并询问。初始时刻你在 $1$ 号点，要去 $n$ 号点。求最少花费的期望。
$1\leq n,m\leq 3\times 10^5$

Solution

$\rm Fibonacci$ 数列的性质很多，有的常考，有的不常考。
这些性质都有可能是解题关键。这里稍作总结。
$\rm Fibonacci$ 的定义很多，本文采取如下的递归定义：

$f_i=\begin{cases}$

Description

给你 $n$ 种颜色的球，每个球有 $k$ 个，把这 $n\times k$ 个球排成一排，把每一种颜色的最左边出现的球涂成白色（初始球不包含白色），求最终有多少种不同的颜色序列，答案对 $10^9+7$ 取模。
$1\leq n,k\leq 2\times 10^3$

Solution

Description

$\rm Link$

Solution

首先分析下样例。

Description

$\rm Link$

Solution

做完这道题感觉对树状数组偏序计数有了全新的认识...🚀

看了 $\sout{\rm{lsqs}}$ 的博客才知道自己容斥原理学的不够深
容斥大概是计数中非常重要的了。以前都是式子直接用，核心的层次大抵是没有接触到，证明的过程也很少看。所以总结一些比较基础的知识和证明过程。以后式子用起来希望能更有底气。🙏

原始公式

Description

给定一张 $n$ 个点 $m$ 条边的图，一条边 $(u,v)$ 有 $\frac{1}{3}$ 的概率消失，$\frac{1}{3}$ 的概率定向成 $u\rightarrow v$ ，$\frac{1}{3}$ 的概率定向成 $v\rightarrow u$ 。求最后的图是 $\rm{DAG}$ 的概率。

$n\leq 20,m\leq \frac{n(n-1)}{2}$

Solution

一个不会整数划分的 sb 的自救

考虑一个这样的问题：给定 $n,m$ ，求将 $m$ 划分成不超过 $n$ 个从 $1$ 开始值域连续的整数的和的方案数。

有一个很明显的做法：设 $f_{i,j,k}$ 表示用了 $i$ 个数，总和为 $j$ ，目前最大数为 $k$ 的方案数。转移比较明显：

Description

$\text{Link}$

Solution

西哥挖坟挖出来一道神仙题。